package 链表;

import java.util.HashMap;
import java.util.HashSet;

public class Solution4 {
    //https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4

/*    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //思路：把值变为-1标记，但收验的时候就是看值的，不能改，空间复杂度O(1)也不能每个再创一个变量装
        ListNode cur = pHead;
        while (cur != null && cur.val != -1) {
            cur.val = -1;
            cur = cur.next;
        }
        *//*if(cur == null) {
            return null;
        }else {
            return cur;
        }*//*
        return cur;
    }*/

    //题解：https://blog.nowcoder.net/n/4994b875bb9a48fe8dded2e0b4e6add3
    public ListNode EntryNodeOfLoop1(ListNode pHead) {
        //思路1：装在一个数据结构里检查是否已装有过
        HashSet<ListNode> map = new HashSet<>();
        ListNode cur = pHead;
        while (cur != null && !map.contains(cur)) {
            map.add(cur);
            cur = cur.next;
        }
        return cur;
    }
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //思路2：从相遇点和头同时走，会在环入口相遇
        ListNode slow = pHead;
        ListNode fast = pHead;
        if(fast == null || fast.next == null) {
            return null;
        }
        fast = fast.next.next;
        slow = slow.next;
        while (fast != null && fast.next != null && fast != slow) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast == null || fast.next == null) {
            return null;
        }
        fast = pHead;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}